package com.school.chapter02.graph_;

import java.util.Scanner;

public class MinimumSpanningTree {

    static int inf = Integer.MAX_VALUE;
    static int[][] tab;
    static int[] vis;
    static int sum = 0;
    static int n;
    static int ans = 0;  // 记录找了几条边

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        System.out.printf("输入村庄个数n:");
        n = scan.nextInt();
        System.out.printf("输入可以连通的路m:");
        int m = scan.nextInt();

        if (m < n - 1) {  // 如果边数小于 n-1 则不可能连通

            System.out.println(-1);
            return;
        }

        tab = new int[n+1][n+1];
        vis = new int[n+1];

        for (int i = 1; i <= n; i++) {  // 初始化邻接矩阵
            for (int j = 1; j <= n; j++) {
                if (i == j) tab[i][j] = 0;
                else tab[i][j] = inf;
            }
        }


        for (int i = 0; i < m; i++) {  // 初始化邻接矩阵,直接连接的边填值
            System.out.printf("输入从a:");
            int a = scan.nextInt();
            System.out.printf("到b:");
            int b = scan.nextInt();
            System.out.printf("的距离w:");
            int w = scan.nextInt();

            tab[a][b] = w;
            tab[b][a] = w;
        }

        prim(1);  // prim

        if (ans == n-1) System.out.println(sum);
        else System.out.println(-1);
    }

    public static void prim(int v){

        vis[v] = 1;

        for (int k = 0; k < n - 1; k++) {  // 需要找 n-1 条边

            int edg = inf;
            int curV= -1;
            boolean flag = false;

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i==j) continue;
                    // i->j节点,i为访问过的,j为未访问的
                    if (vis[i]==1 && vis[j]==0 && tab[i][j] < edg){
                        edg = tab[i][j];  // 最短边
                        curV = j;  // 重新找到的点
                        flag = true;
                    }
                }
            }

            if (flag) ans++;  // 这次循环找到边就ans++,否则就提前终止
            else return;

            sum += edg;
            vis[curV] = 1;  // 标记未已经访问
        }
    }
}
